package top.fengleifeng.question;

/**
 * @program: leetcode-test
 * @description:
 * @author: fengleifeng
 * @create: 2020-09-22 19:56
 **/
public class Num198打家劫舍 {
    // 第一个 长度   第二个 0代表没有选择这一位，1代表选择这一位的最大值
    class Solution {
        public int rob(int[] nums) {
            int numsLength = nums.length;
            if (numsLength <= 0) {
                return 0;
            }
            int[][] dps = new int[numsLength][2];
            dps[0][0] = 0;
            dps[0][1] = nums[0];
            for (int i = 1; i < numsLength; i++) {
                dps[i][0] = Math.max(dps[i - 1][0], dps[i - 1][1]);
                dps[i][1] = Math.max(dps[i - 1][0] + nums[i], dps[i - 1][1]);
            }
            return Math.max(dps[numsLength - 1][0], dps[numsLength - 1][1]);
        }
    }

    class Solution2 {
        public int rob(int[] nums) {
            int[] dps = new int[nums.length];
            return dp(nums, 0,dps);
        }

        private int dp(int[] nums, int start, int[] dps) {
            if (start >= nums.length) {
                return 0;
            }
            int max = Math.max(dp(nums, start + 1, dps), dp(nums, start + 2, dps) + nums[start]);
            dps[start] = max;
            return max;
        }
    }

    public static void main(String[] args) {
        int[] ints = {2, 7, 9, 3, 1};
        int rob = new Num198打家劫舍().new Solution().rob(ints);
        System.out.println(rob);
        int rob2 = new Num198打家劫舍().new Solution2().rob(ints);
        System.out.println(rob2);
    }
}
